//
// Created by lxinp on 2022/8/17.
//

#ifndef DATASTRUCTURE_HEAP_H
#define DATASTRUCTURE_HEAP_H


/**
 * Heap (priority queue) with an array implementation
 * Index 0 is dummy; left_child is 2i, right_child is 2i+1
 * Parent is i/2, root is 1, the next free position is n+1
 * @tparam T
 */
template<typename T>
class Heap {
public:
    Heap();
    Heap(const T* array, int length);  // O(n) implementation
    ~Heap();
    T get_min();
    void remove_top();
    void insert(const T& data);
    int size() const;
    void print() const;
private:
    T* arr;
    int n;  // number of elements currently stored
    int max_size;
    void resize();
    bool is_empty() const;
    bool is_full() const;
    void heapify_up(int loc);
    void heapify_down(int loc);
};


#endif //DATASTRUCTURE_HEAP_H
